{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 发现群组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用feedparser解析RSS订阅源"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import feedparser\n",
    "import re\n",
    "\n",
    "# Returns title and dictionary of word counts for an RSS feed\n",
    "def getwordcounts(url):\n",
    "  # Parse the feed\n",
    "  d=feedparser.parse(url)\n",
    "  wc={}\n",
    "\n",
    "  # Loop over all the entries\n",
    "  for e in d.entries:\n",
    "    if 'summary' in e: \n",
    "        summary=e.summary\n",
    "    else: \n",
    "        summary=e.description\n",
    "\n",
    "    # Extract a list of words\n",
    "    words=getwords(e.title+' '+summary)\n",
    "    for word in words:\n",
    "      wc.setdefault(word,0)\n",
    "      wc[word]+=1\n",
    "  return d.feed.title,wc\n",
    "\n",
    "def getwords(html):\n",
    "  # Remove all the HTML tags\n",
    "  txt=re.compile(r'<[^>]+>').sub('',html)\n",
    "\n",
    "  # Split words by all non-alpha characters\n",
    "  words=re.compile(r'[^A-Z^a-z]+').split(txt)\n",
    "\n",
    "  # Convert to lowercase\n",
    "  return [word.lower() for word in words if word!='']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解析并准备数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Failed to parse feed http://feeds.feedburner.com/37signals/beMH\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/blogspot/bRuz\n",
      "\n",
      "Failed to parse feed http://battellemedia.com/index.xml\n",
      "\n",
      "Failed to parse feed http://feeds.searchenginewatch.com/sewblog\n",
      "\n",
      "Failed to parse feed http://blog.topix.net/index.rdf\n",
      "\n",
      "Failed to parse feed http://blogs.abcnews.com/theblotter/index.rdf\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/ConsumingExperienceFull\n",
      "\n",
      "Failed to parse feed http://flagrantdisregard.com/index.php/feed/\n",
      "\n",
      "Failed to parse feed http://featured.gigaom.com/feed/\n",
      "\n",
      "Failed to parse feed http://gofugyourself.typepad.com/go_fug_yourself/index.rdf\n",
      "\n",
      "Failed to parse feed http://googleblog.blogspot.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/GoogleOperatingSystem\n",
      "\n",
      "Failed to parse feed http://headrush.typepad.com/creating_passionate_users/index.rdf\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/instapundit/main\n",
      "\n",
      "Failed to parse feed http://jeremy.zawodny.com/blog/rss2.xml\n",
      "\n",
      "Failed to parse feed http://joi.ito.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/Mashable\n",
      "\n",
      "Failed to parse feed http://michellemalkin.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://moblogsmoproblems.blogspot.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://beta.blogger.com/feeds/27154654/posts/full?alt=rss\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/paulstamatiou\n",
      "\n",
      "Failed to parse feed http://powerlineblog.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/Publishing20\n",
      "\n",
      "Failed to parse feed http://scienceblogs.com/pharyngula/index.xml\n",
      "\n",
      "Failed to parse feed http://scobleizer.wordpress.com/feed/\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/andrewsullivan/rApM\n",
      "\n",
      "Failed to parse feed http://wilwheaton.typepad.com/wwdnbackup/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.43folders.com/feed/\n",
      "\n",
      "Failed to parse feed http://www.456bereastreet.com/feed.xml\n",
      "\n",
      "Failed to parse feed http://www.bloggersblog.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://www.bloglines.com/rss/about/news\n",
      "\n",
      "Failed to parse feed http://www.buzzmachine.com/index.xml\n",
      "\n",
      "Failed to parse feed http://www.coolhunting.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/crooksandliars/YaCP\n",
      "\n",
      "Failed to parse feed http://www.downloadsquad.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://www.gapingvoid.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.gawker.com/index.xml\n",
      "\n",
      "Failed to parse feed http://www.joystiq.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://feeds.kottke.org/main\n",
      "\n",
      "Failed to parse feed http://littlegreenfootballs.com/weblog/lgf-rss.php\n",
      "\n",
      "Failed to parse feed http://www.makezine.com/blog/index.xml\n",
      "\n",
      "Failed to parse feed http://xml.metafilter.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://www.micropersuasion.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.oilman.ca/feed/\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/QuickOnlineTips\n",
      "\n",
      "Failed to parse feed http://www.readwriteweb.com/rss.xml\n",
      "\n",
      "Failed to parse feed http://scienceblogs.com/sample/combined.xml\n",
      "\n",
      "Failed to parse feed http://www.sifry.com/alerts/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.simplebits.com/xml/rss.xml\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/Spikedhumor\n",
      "\n",
      "Failed to parse feed http://www.talkingpointsmemo.com/index.xml\n",
      "\n",
      "Failed to parse feed http://feeds.feedburner.com/TechCrunch\n",
      "\n",
      "Failed to parse feed http://www.techeblog.com/index.php/feed/\n",
      "\n",
      "Failed to parse feed http://www.thesuperficial.com/index.xml\n",
      "\n",
      "Failed to parse feed http://www.treehugger.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.valleywag.com/index.xml\n",
      "\n",
      "Failed to parse feed http://www.we-make-money-not-art.com/index.rdf\n",
      "\n",
      "Failed to parse feed http://www.wonkette.com/index.xml\n",
      "\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'file' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-10-f437631858de>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     19\u001b[0m     \u001b[0mwordlist\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mw\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 21\u001b[0;31m \u001b[0mout\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mfile\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'blogdata1.txt'\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m'w'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     22\u001b[0m \u001b[0mout\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Blog'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     23\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mword\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mwordlist\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mout\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'\\t%s'\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mword\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'file' is not defined"
     ]
    }
   ],
   "source": [
    "apcount={}\n",
    "wordcounts={}\n",
    "feedlist=[line for line in open('feedlist.txt')]\n",
    "for feedurl in feedlist:\n",
    "  try:\n",
    "    title,wc=getwordcounts(feedurl)\n",
    "    wordcounts[title]=wc\n",
    "    for word,count in wc.items():\n",
    "      apcount.setdefault(word,0)\n",
    "      if count>1:\n",
    "        apcount[word]+=1\n",
    "  except:\n",
    "    print ('Failed to parse feed %s' % feedurl)\n",
    "\n",
    "wordlist=[]\n",
    "for w,bc in apcount.items():\n",
    "  frac=float(bc)/len(feedlist)\n",
    "  if frac>0.1 and frac<0.5:\n",
    "    wordlist.append(w)\n",
    "\n",
    "out=open('blogdata1.txt','w')\n",
    "out.write('Blog')\n",
    "for word in wordlist: out.write('\\t%s' % word)\n",
    "out.write('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 读取数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def readfile(filename):\n",
    "  lines=[line for line in open(filename)]\n",
    "  \n",
    "  # First line is the column titles\n",
    "  colnames=lines[0].strip().split('\\t')[1:]\n",
    "  rownames=[]\n",
    "  data=[]\n",
    "  for line in lines[1:]:\n",
    "    p=line.strip().split('\\t')\n",
    "    # First column in each row is the rowname\n",
    "    rownames.append(p[0])\n",
    "    # The data for this row is the remainder of the row\n",
    "    data.append([float(x) for x in p[1:]])\n",
    "  return rownames,colnames,data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 皮尔逊相关度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "\n",
    "def pearson(v1,v2):\n",
    "  # Simple sums\n",
    "  sum1=sum(v1)\n",
    "  sum2=sum(v2)\n",
    "  \n",
    "  # Sums of the squares\n",
    "  sum1Sq=sum([pow(v,2) for v in v1])\n",
    "  sum2Sq=sum([pow(v,2) for v in v2])\t\n",
    "  \n",
    "  # Sum of the products\n",
    "  pSum=sum([v1[i]*v2[i] for i in range(len(v1))])\n",
    "  \n",
    "  # Calculate r (Pearson score)\n",
    "  num=pSum-(sum1*sum2/len(v1))\n",
    "  den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))\n",
    "  if den==0: return 0\n",
    "\n",
    "  return 1.0-num/den"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 定义聚类class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class bicluster:\n",
    "  def __init__(self,vec,left=None,right=None,distance=0.0,id=None):\n",
    "    self.left=left\n",
    "    self.right=right\n",
    "    self.vec=vec\n",
    "    self.id=id\n",
    "    self.distance=distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 分级聚类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hcluster(rows,distance=pearson):\n",
    "  distances={}\n",
    "  currentclustid=-1\n",
    "\n",
    "  # Clusters are initially just the rows\n",
    "  clust=[bicluster(rows[i],id=i) for i in range(len(rows))]\n",
    "\n",
    "  while len(clust)>1:\n",
    "    lowestpair=(0,1)\n",
    "    closest=distance(clust[0].vec,clust[1].vec)\n",
    "\n",
    "    # loop through every pair looking for the smallest distance\n",
    "    for i in range(len(clust)):\n",
    "      for j in range(i+1,len(clust)):\n",
    "        # distances is the cache of distance calculations\n",
    "        if (clust[i].id,clust[j].id) not in distances: \n",
    "          distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)\n",
    "\n",
    "        d=distances[(clust[i].id,clust[j].id)]\n",
    "\n",
    "        if d<closest:\n",
    "          closest=d\n",
    "          lowestpair=(i,j)\n",
    "\n",
    "    # calculate the average of the two clusters\n",
    "    mergevec=[\n",
    "    (clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0 \n",
    "    for i in range(len(clust[0].vec))]\n",
    "\n",
    "    # create the new cluster\n",
    "    newcluster=bicluster(mergevec,left=clust[lowestpair[0]],\n",
    "                         right=clust[lowestpair[1]],\n",
    "                         distance=closest,id=currentclustid)\n",
    "\n",
    "    # cluster ids that weren't in the original set are negative\n",
    "    currentclustid-=1\n",
    "    del clust[lowestpair[1]]\n",
    "    del clust[lowestpair[0]]\n",
    "    clust.append(newcluster)\n",
    "\n",
    "  return clust[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "blognames, words, data = readfile('blogdata.txt')\n",
    "clust = hcluster(data)\n",
    "#printclust(clust, labels=blognames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 打印分级聚类层级结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def printclust(clust,labels=None,n=0):\n",
    "  # indent to make a hierarchy layout\n",
    "  for i in range(n): print (' ', end='')\n",
    "  if clust.id<0:\n",
    "    # negative id means that this is branch\n",
    "    print ('-')\n",
    "  else:\n",
    "    # positive id means that this is an endpoint\n",
    "    if labels==None: print (clust.id)\n",
    "    else: print (labels[clust.id])\n",
    "\n",
    "  # now print the right and left branches\n",
    "  if clust.left!=None: printclust(clust.left,labels=labels,n=n+1)\n",
    "  if clust.right!=None: printclust(clust.right,labels=labels,n=n+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-\n",
      " gapingvoid: \"cartoons drawn on the back of business cards\"\n",
      " -\n",
      "  -\n",
      "   Schneier on Security\n",
      "   Instapundit.com\n",
      "  -\n",
      "   The Blotter\n",
      "   -\n",
      "    -\n",
      "     MetaFilter\n",
      "     -\n",
      "      SpikedHumor\n",
      "      -\n",
      "       Captain's Quarters\n",
      "       -\n",
      "        Michelle Malkin\n",
      "        -\n",
      "         -\n",
      "          NewsBusters.org - Exposing Liberal Media Bias\n",
      "          -\n",
      "           -\n",
      "            Hot Air\n",
      "            Crooks and Liars\n",
      "           -\n",
      "            Power Line\n",
      "            Think Progress\n",
      "         -\n",
      "          Andrew Sullivan | The Daily Dish\n",
      "          -\n",
      "           Little Green Footballs\n",
      "           -\n",
      "            Eschaton\n",
      "            -\n",
      "             Talking Points Memo: by Joshua Micah Marshall\n",
      "             Daily Kos\n",
      "    -\n",
      "     43 Folders\n",
      "     -\n",
      "      TechEBlog\n",
      "      -\n",
      "       -\n",
      "        Mashable!\n",
      "        Signum sine tinnitu--by Guy Kawasaki\n",
      "       -\n",
      "        -\n",
      "         -\n",
      "          Slashdot\n",
      "          -\n",
      "           MAKE Magazine\n",
      "           Boing Boing\n",
      "         -\n",
      "          -\n",
      "           Oilman\n",
      "           -\n",
      "            Online Marketing Report\n",
      "            -\n",
      "             Treehugger\n",
      "             -\n",
      "              SimpleBits\n",
      "              -\n",
      "               Cool Hunting\n",
      "               -\n",
      "                Steve Pavlina's Personal Development Blog\n",
      "                -\n",
      "                 -\n",
      "                  ScienceBlogs : Combined Feed\n",
      "                  Pharyngula\n",
      "                 -\n",
      "                  BuzzMachine\n",
      "                  -\n",
      "                   Copyblogger\n",
      "                   -\n",
      "                    -\n",
      "                     The Viral Garden\n",
      "                     Seth's Blog\n",
      "                    -\n",
      "                     -\n",
      "                      Bloggers Blog: Blogging the Blogsphere\n",
      "                      -\n",
      "                       Sifry's Alerts\n",
      "                       ProBlogger Blog Tips\n",
      "                     -\n",
      "                      -\n",
      "                       Valleywag\n",
      "                       Scobleizer - Tech Geek Blogger\n",
      "                      -\n",
      "                       -\n",
      "                        O'Reilly Radar\n",
      "                        456 Berea Street\n",
      "                       -\n",
      "                        Lifehacker\n",
      "                        -\n",
      "                         Quick Online Tips\n",
      "                         -\n",
      "                          Publishing 2.0\n",
      "                          -\n",
      "                           Micro Persuasion\n",
      "                           -\n",
      "                            A Consuming Experience (full feed)\n",
      "                            -\n",
      "                             John Battelle's Searchblog\n",
      "                             -\n",
      "                              Search Engine Watch Blog\n",
      "                              -\n",
      "                               Read/WriteWeb\n",
      "                               -\n",
      "                                Official Google Blog\n",
      "                                -\n",
      "                                 Search Engine Roundtable\n",
      "                                 -\n",
      "                                  Google Operating System\n",
      "                                  Google Blogoscoped\n",
      "          -\n",
      "           -\n",
      "            -\n",
      "             -\n",
      "              Blog Maverick\n",
      "              -\n",
      "               Download Squad\n",
      "               -\n",
      "                CoolerHeads Prevail\n",
      "                -\n",
      "                 Joystiq\n",
      "                 The Unofficial Apple Weblog (TUAW)\n",
      "             -\n",
      "              Autoblog\n",
      "              -\n",
      "               Engadget\n",
      "               TMZ.com\n",
      "            -\n",
      "             Matt Cutts: Gadgets, Google, and SEO\n",
      "             -\n",
      "              PaulStamatiou.com\n",
      "              -\n",
      "               -\n",
      "                GigaOM\n",
      "                TechCrunch\n",
      "               -\n",
      "                -\n",
      "                 Techdirt\n",
      "                 Creating Passionate Users\n",
      "                -\n",
      "                 Joho the Blog\n",
      "                 -\n",
      "                  -\n",
      "                   PerezHilton.com\n",
      "                   Jeremy Zawodny's blog\n",
      "                  -\n",
      "                   Joi Ito's Web\n",
      "                   -\n",
      "                    ongoing\n",
      "                    -\n",
      "                     Joel on Software\n",
      "                     -\n",
      "                      -\n",
      "                       we make money not art\n",
      "                       -\n",
      "                        plasticbag.org\n",
      "                        -\n",
      "                         Signal vs. Noise\n",
      "                         -\n",
      "                          kottke.org\n",
      "                          -\n",
      "                           Neil Gaiman's Journal\n",
      "                           -\n",
      "                            -\n",
      "                             The Huffington Post | Raw Feed\n",
      "                             -\n",
      "                              Wonkette\n",
      "                              -\n",
      "                               Gawker\n",
      "                               -\n",
      "                                The Superficial - Because You're Ugly\n",
      "                                Go Fug Yourself\n",
      "                            -\n",
      "                             Deadspin\n",
      "                             Gothamist\n",
      "                      -\n",
      "                       Kotaku\n",
      "                       Gizmodo\n",
      "           -\n",
      "            Shoemoney - Skills to pay the bills\n",
      "            -\n",
      "             flagrantdisregard\n",
      "             -\n",
      "              WWdN: In Exile\n",
      "              -\n",
      "               Derek Powazek\n",
      "               -\n",
      "                lifehack.org\n",
      "                Dave Shea's mezzoblue\n",
      "        -\n",
      "         Wired News: Top Stories\n",
      "         -\n",
      "          Topix.net Weblog\n",
      "          Bloglines | News\n"
     ]
    }
   ],
   "source": [
    "printclust(clust, labels=blognames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 绘制分级聚类的结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from PIL import Image, ImageDraw\n",
    "\n",
    "def getheight(clust):\n",
    "  # Is this an endpoint? Then the height is just 1\n",
    "  if clust.left==None and clust.right==None: return 1\n",
    "\n",
    "  # Otherwise the height is the same of the heights of\n",
    "  # each branch\n",
    "  return getheight(clust.left)+getheight(clust.right)\n",
    "\n",
    "def getdepth(clust):\n",
    "  # The distance of an endpoint is 0.0\n",
    "  if clust.left==None and clust.right==None: return 0\n",
    "\n",
    "  # The distance of a branch is the greater of its two sides\n",
    "  # plus its own distance\n",
    "  return max(getdepth(clust.left),getdepth(clust.right))+clust.distance\n",
    "\n",
    "\n",
    "def drawdendrogram(clust,labels,jpeg='clusters.jpg'):\n",
    "  # height and width\n",
    "  h=getheight(clust)*20\n",
    "  w=1200\n",
    "  depth=getdepth(clust)\n",
    "\n",
    "  # width is fixed, so scale distances accordingly\n",
    "  scaling=float(w-150)/depth\n",
    "\n",
    "  # Create a new image with a white background\n",
    "  img=Image.new('RGB',(w,h),(255,255,255))\n",
    "  draw=ImageDraw.Draw(img)\n",
    "\n",
    "  draw.line((0,h/2,10,h/2),fill=(255,0,0))    \n",
    "\n",
    "  # Draw the first node\n",
    "  drawnode(draw,clust,10,(h/2),scaling,labels)\n",
    "  img.save(jpeg,'JPEG')\n",
    "\n",
    "def drawnode(draw,clust,x,y,scaling,labels):\n",
    "  if clust.id<0:\n",
    "    h1=getheight(clust.left)*20\n",
    "    h2=getheight(clust.right)*20\n",
    "    top=y-(h1+h2)/2\n",
    "    bottom=y+(h1+h2)/2\n",
    "    # Line length\n",
    "    ll=clust.distance*scaling\n",
    "    # Vertical line from this cluster to children    \n",
    "    draw.line((x,top+h1/2,x,bottom-h2/2),fill=(255,0,0))    \n",
    "    \n",
    "    # Horizontal line to left item\n",
    "    draw.line((x,top+h1/2,x+ll,top+h1/2),fill=(255,0,0))    \n",
    "\n",
    "    # Horizontal line to right item\n",
    "    draw.line((x,bottom-h2/2,x+ll,bottom-h2/2),fill=(255,0,0))        \n",
    "\n",
    "    # Call the function to draw the left and right nodes    \n",
    "    drawnode(draw,clust.left,x+ll,top+h1/2,scaling,labels)\n",
    "    drawnode(draw,clust.right,x+ll,bottom-h2/2,scaling,labels)\n",
    "  else:   \n",
    "    # If this is an endpoint, draw the item label\n",
    "    draw.text((x+5,y-7),labels[clust.id],(0,0,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图片保存至本地"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "drawdendrogram(clust, blognames, jpeg='blogclust.jpg')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 行和列对调，对单词聚类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rotatematrix(data):\n",
    "  newdata=[]\n",
    "  for i in range(len(data[0])):\n",
    "    newrow=[data[j][i] for j in range(len(data))]\n",
    "    newdata.append(newrow)\n",
    "  return newdata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rdata = rotatematrix(data)\n",
    "wordclust = hcluster(rdata)\n",
    "drawdendrogram(wordclust, labels=words, jpeg='wordclust.jpg')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### k均值聚类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def kcluster(rows,distance=pearson,k=4):\n",
    "  # Determine the minimum and maximum values for each point\n",
    "  ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) \n",
    "  for i in range(len(rows[0]))]\n",
    "\n",
    "  # Create k randomly placed centroids\n",
    "  clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0] \n",
    "  for i in range(len(rows[0]))] for j in range(k)]\n",
    "  \n",
    "  lastmatches=None\n",
    "  for t in range(100):\n",
    "    print('Iteration %d' % t)\n",
    "    bestmatches=[[] for i in range(k)]\n",
    "    \n",
    "    # Find which centroid is the closest for each row\n",
    "    for j in range(len(rows)):\n",
    "      row=rows[j]\n",
    "      bestmatch=0\n",
    "      for i in range(k):\n",
    "        d=distance(clusters[i],row)\n",
    "        if d<distance(clusters[bestmatch],row): bestmatch=i\n",
    "      bestmatches[bestmatch].append(j)\n",
    "\n",
    "    # If the results are the same as last time, this is complete\n",
    "    if bestmatches==lastmatches: break\n",
    "    lastmatches=bestmatches\n",
    "    \n",
    "    # Move the centroids to the average of their members\n",
    "    for i in range(k):\n",
    "      avgs=[0.0]*len(rows[0])\n",
    "      if len(bestmatches[i])>0:\n",
    "        for rowid in bestmatches[i]:\n",
    "          for m in range(len(rows[rowid])):\n",
    "            avgs[m]+=rows[rowid][m]\n",
    "        for j in range(len(avgs)):\n",
    "          avgs[j]/=len(bestmatches[i])\n",
    "        clusters[i]=avgs\n",
    "      \n",
    "  return bestmatches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 0\n",
      "Iteration 1\n",
      "Iteration 2\n",
      "Iteration 3\n",
      "Iteration 4\n",
      "Iteration 5\n",
      "[[41, 42, 46, 81], [2, 7, 16, 23, 24, 25, 34, 36, 40, 48, 49, 56, 79, 80, 85, 91, 94], [27, 37, 51, 53, 64, 71, 90], [4, 5, 45], [11, 63, 82, 95], [6, 10, 14, 21, 26, 29, 59, 60, 69, 70, 73, 74, 75, 87, 92, 97], [0, 1, 3, 9, 15, 18, 19, 20, 22, 28, 31, 38, 39, 43, 47, 61, 72, 86, 88, 93, 98], [13, 32, 33, 35, 44, 54, 57, 62, 67, 76, 78, 83, 84, 96], [8, 12, 52, 65, 66, 68, 77], [17, 30, 50, 55, 58, 89]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['Publishing 2.0',\n",
       " 'GigaOM',\n",
       " \"John Battelle's Searchblog\",\n",
       " 'Lifehacker',\n",
       " 'Google Operating System',\n",
       " 'Valleywag',\n",
       " 'Topix.net Weblog',\n",
       " 'Micro Persuasion',\n",
       " 'Search Engine Watch Blog',\n",
       " 'Techdirt',\n",
       " 'Official Google Blog',\n",
       " 'Search Engine Roundtable',\n",
       " 'A Consuming Experience (full feed)',\n",
       " 'Matt Cutts: Gadgets, Google, and SEO',\n",
       " 'Quick Online Tips',\n",
       " 'Google Blogoscoped',\n",
       " 'Read/WriteWeb']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kclust=kcluster(data, k=10)\n",
    "print(kclust)\n",
    "[blognames[r] for r in kclust[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# from BeautifulSoup import BeautifulSoup\n",
    "# import urllib2\n",
    "# import re\n",
    "# chare=re.compile(r'[!-\\.&]')\n",
    "# itemowners={}\n",
    "\n",
    "# # Words to remove\n",
    "# dropwords=['a','new','some','more','my','own','the','many','other','another']\n",
    "\n",
    "# currentuser=0\n",
    "# for i in range(1,51):\n",
    "#   # URL for the want search page\n",
    "#   c=urllib2.urlopen(\n",
    "#   'http://member.zebo.com/Main?event_key=USERSEARCH&wiowiw=wiw&keyword=car&page=%d'\n",
    "#   % (i))\n",
    "#   soup=BeautifulSoup(c.read())\n",
    "#   for td in soup('td'):\n",
    "#     # Find table cells of bgverdanasmall class\n",
    "#     if ('class' in dict(td.attrs) and td['class']=='bgverdanasmall'):\n",
    "#       items=[re.sub(chare,'',str(a.contents[0]).lower()).strip() for a in td('a')]\n",
    "#       for item in items:\n",
    "#         # Remove extra words\n",
    "#         txt=' '.join([t for t in item.split(' ') if t not in dropwords])\n",
    "#         if len(txt)<2: continue\n",
    "#         itemowners.setdefault(txt,{})\n",
    "#         itemowners[txt][currentuser]=1\n",
    "#       currentuser+=1\n",
    "      \n",
    "# out=open('zebo.txt','w')\n",
    "# out.write('Item')\n",
    "# for user in range(0,currentuser): out.write('\\tU%d' % user)\n",
    "# out.write('\\n')\n",
    "# for item,owners in itemowners.items():\n",
    "#   if len(owners)>10:\n",
    "#     out.write(item)\n",
    "#     for user in range(0,currentuser):\n",
    "#       if user in owners: out.write('\\t1')\n",
    "#       else: out.write('\\t0')\n",
    "#     out.write('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tanamoto(v1,v2):\n",
    "  c1,c2,shr=0,0,0\n",
    "  \n",
    "  for i in range(len(v1)):\n",
    "    if v1[i]!=0: c1+=1 # in v1\n",
    "    if v2[i]!=0: c2+=1 # in v2\n",
    "    if v1[i]!=0 and v2[i]!=0: shr+=1 # in both\n",
    "  \n",
    "  return 1.0-(float(shr)/(c1+c2-shr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wants, people, data = readfile('zebo.txt')\n",
    "clust = hcluster(data, distance=tanamoto)\n",
    "drawdendrogram(clust, wants)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def scaledown(data,distance=pearson,rate=0.01):\n",
    "  n=len(data)\n",
    "\n",
    "  # The real distances between every pair of items\n",
    "  realdist=[[distance(data[i],data[j]) for j in range(n)] \n",
    "             for i in range(0,n)]\n",
    "\n",
    "  # Randomly initialize the starting points of the locations in 2D\n",
    "  loc=[[random.random(),random.random()] for i in range(n)]\n",
    "  fakedist=[[0.0 for j in range(n)] for i in range(n)]\n",
    "  \n",
    "  lasterror=None\n",
    "  for m in range(0,1000):\n",
    "    # Find projected distances\n",
    "    for i in range(n):\n",
    "      for j in range(n):\n",
    "        fakedist[i][j]=sqrt(sum([pow(loc[i][x]-loc[j][x],2) \n",
    "                                 for x in range(len(loc[i]))]))\n",
    "  \n",
    "    # Move points\n",
    "    grad=[[0.0,0.0] for i in range(n)]\n",
    "    \n",
    "    totalerror=0\n",
    "    for k in range(n):\n",
    "      for j in range(n):\n",
    "        if j==k: continue\n",
    "        # The error is percent difference between the distances\n",
    "        errorterm=(fakedist[j][k]-realdist[j][k])/realdist[j][k]\n",
    "        \n",
    "        # Each point needs to be moved away from or towards the other\n",
    "        # point in proportion to how much error it has\n",
    "        grad[k][0]+=((loc[k][0]-loc[j][0])/fakedist[j][k])*errorterm\n",
    "        grad[k][1]+=((loc[k][1]-loc[j][1])/fakedist[j][k])*errorterm\n",
    "\n",
    "        # Keep track of the total error\n",
    "        totalerror+=abs(errorterm)\n",
    "    print (totalerror)\n",
    "\n",
    "    # If the answer got worse by moving the points, we are done\n",
    "    if lasterror and lasterror<totalerror: break\n",
    "    lasterror=totalerror\n",
    "    \n",
    "    # Move each of the points by the learning rate times the gradient\n",
    "    for k in range(n):\n",
    "      loc[k][0]-=rate*grad[k][0]\n",
    "      loc[k][1]-=rate*grad[k][1]\n",
    "\n",
    "  return loc\n",
    "\n",
    "def draw2d(data,labels,jpeg='mds2d.jpg'):\n",
    "  img=Image.new('RGB',(2000,2000),(255,255,255))\n",
    "  draw=ImageDraw.Draw(img)\n",
    "  for i in range(len(data)):\n",
    "    x=(data[i][0]+0.5)*1000\n",
    "    y=(data[i][1]+0.5)*1000\n",
    "    draw.text((x,y),labels[i],(0,0,0))\n",
    "  img.save(jpeg,'JPEG')  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4296.813892193015\n",
      "3628.4864275905925\n",
      "3539.9081903644365\n",
      "3496.6166105924863\n",
      "3462.7290404176338\n",
      "3434.0328664143385\n",
      "3408.236895515862\n",
      "3383.3359804875063\n",
      "3360.7886350498316\n",
      "3336.1964089267813\n",
      "3313.4711976526255\n",
      "3295.224475023654\n",
      "3281.0366360090225\n",
      "3269.6265717178503\n",
      "3259.4811554606395\n",
      "3250.389440066609\n",
      "3241.0664667185256\n",
      "3231.575993216872\n",
      "3222.268863578611\n",
      "3213.701241084538\n",
      "3205.189172449979\n",
      "3197.3486443875404\n",
      "3189.3872718758\n",
      "3180.9782691460023\n",
      "3173.161101086121\n",
      "3166.2969224747035\n",
      "3159.9086130969404\n",
      "3153.920010543945\n",
      "3148.0167634208096\n",
      "3142.4107270953377\n",
      "3137.0723402399854\n",
      "3132.1321180264813\n",
      "3127.244744666289\n",
      "3122.166704704863\n",
      "3116.7227530286677\n",
      "3112.240840396887\n",
      "3108.6612665322486\n",
      "3105.091928844856\n",
      "3101.5620024067334\n",
      "3098.5136870516308\n",
      "3095.212774805188\n",
      "3092.012882963618\n",
      "3089.2729808240756\n",
      "3086.8356468842285\n",
      "3084.5255797492327\n",
      "3082.414360715347\n",
      "3080.3366120191386\n",
      "3078.377211447293\n",
      "3076.6835619171598\n",
      "3075.105322679719\n",
      "3073.5661928330665\n",
      "3072.118009733593\n",
      "3070.6632880113502\n",
      "3069.0103309472697\n",
      "3067.1784668273312\n",
      "3065.2426155025773\n",
      "3063.3288206600096\n",
      "3061.6700246128894\n",
      "3060.100566802373\n",
      "3058.5623539393127\n",
      "3057.0154650313702\n",
      "3055.545782213329\n",
      "3054.096689326921\n",
      "3052.751964959042\n",
      "3051.4993834107945\n",
      "3050.4520519753014\n",
      "3049.4955852081675\n",
      "3048.436164801163\n",
      "3047.3965508493675\n",
      "3046.476114036981\n",
      "3045.6292813102777\n",
      "3044.773199906265\n",
      "3044.0494751656047\n",
      "3043.33143470877\n",
      "3042.6472062236494\n",
      "3041.976691092668\n",
      "3041.306046068\n",
      "3040.7141564114404\n",
      "3040.204887372824\n",
      "3039.6379863152565\n",
      "3039.153886835963\n",
      "3038.811695118058\n",
      "3038.4700033501\n",
      "3038.246908024368\n",
      "3037.888758862824\n",
      "3037.5896769480937\n",
      "3037.2678999095024\n",
      "3037.0208135321764\n",
      "3036.64855442299\n",
      "3036.258144568548\n",
      "3035.895747823057\n",
      "3035.5135135411197\n",
      "3035.1494875292856\n",
      "3034.7458720959917\n",
      "3034.338114466803\n",
      "3033.998014994589\n",
      "3033.6378841752876\n",
      "3033.318804559999\n",
      "3033.045682097811\n",
      "3032.7943293259077\n",
      "3032.557016035175\n",
      "3032.3934792690134\n",
      "3032.2150879555466\n",
      "3031.9971117886844\n",
      "3031.7131145451644\n",
      "3031.3985175643206\n",
      "3031.0313024471916\n",
      "3030.6746736997065\n",
      "3030.288603574508\n",
      "3029.880362173227\n",
      "3029.527697417768\n",
      "3029.360170022805\n",
      "3029.224056703135\n",
      "3029.0145340117274\n",
      "3028.8183265212588\n",
      "3028.7189498679\n",
      "3028.5936918185457\n",
      "3028.4538665930486\n",
      "3028.290560677093\n",
      "3028.1075434631452\n",
      "3028.000113218586\n",
      "3027.9211710703235\n",
      "3027.8764478460885\n",
      "3027.843444891853\n",
      "3027.815039351675\n",
      "3027.837420442554\n"
     ]
    }
   ],
   "source": [
    "blognames, words, data = readfile('blogdata.txt')\n",
    "coords = scaledown(data, rate=0.01)\n",
    "draw2d(coords, blognames, jpeg='blogs2d.jpg')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
